#pragma once
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

//namespace xlf
//{
//	template<class T>
//	class stack0
//	{
//	public:
//		stack0(){}
//
//		void push(const T& x){_v.push_back(x);}
//
//		void pop(){	_v.pop_back();}
//
//		T& top() { return _v.back(); }
//		
//		const T& top() const { return _v.back(); }
//
//		size_t size() const { return _v.size(); }
//
//		bool empty() const { return _v.empty(); }
//
//	private:
//		std::vector<T> _v;
//	};
//}
//
//namespace xlf
//{
//	// 适配器模式 -- 封装转换
//	// 迭代器模式 -- 封装统一访问方式（数据结构访问都可以用）
//	template<class T, class Container = deque<T>>
//	class stack
//	{
//	public:
//		stack(){}
//
//		void push(const T& x){_con.push_back(x);}
//
//		void pop(){_con.pop_back();}
//
//		const T& top(){return _con.back();}
//
//		size_t size(){return _con.size();}
//
//		bool empty(){return _con.empty();}
//
//	private:
//		Container _con;
//	};
//}
//
//namespace xlf
//{
//	//只能用deque list适配
//	//用vector会报错，队尾插入，队头删除，
//	//queue不支持头删（先进先出）（没有直接支持，可以用erase）
//	template<class T, class Container = deque<T>>
//	class queue
//	{
//	public:
//		//构造
//		queue()
//		{}
//
//		void push(const T& x)
//		{
//			_con.push_back(x);
//		}
//
//		void pop()
//		{
//			//这样就可以支持vector了，但是效率就很低了
//			//_con.erase(_con.begin());
//
//			_con.pop_front();
//		}
//
//		const T& front()
//		{
//			return _con.front();
//		}
//
//		const T& back()
//		{
//			return _con.back();
//		}
//
//		size_t size()
//		{
//			return _con.size();
//		}
//
//		bool empty()
//		{
//			return _con.empty();
//		}
//
//
//
//	private:
//		Container  _con;
//	};
//}

//namespace xlf
//{
//	template<class T, class Container = vector<T>>
//	class priority_queue
//	{
//	public:
//		// 大堆
//		void adjust_up(int child)
//		{
//			int parent = (child - 1) / 2;
//			while (child > 0)
//			{
//				if (_con[parent] < _con[child])
//				{
//					swap(_con[parent], _con[child]);
//					child = parent;
//					parent = (child - 1) / 2;
//				}
//				else
//				{
//					break;
//				}
//			}
//		}
//
//		void push(const T& x)
//		{
//			_con.push_back(x);
//			adjust_up(_con.size() - 1);//排序的区间长度
//		}
//
//		void adjust_down(size_t parent)
//		{
//			size_t child = parent * 2 + 1;//左孩子
//			while (child < _con.size())
//			{
//				//假设法
//				//选择左右孩子大的那个
//				if (child + 1 < _con.size() && _con[child] < _con[child + 1])
//					//判断是否有右孩子              如果右孩子大就选择右孩子
//				{
//					++child;
//				}
//				if (_con[parent] < _con[child])//孩节点大就交换
//				{
//					swap(_con[parent], _con[child]);
//					parent = child;
//					child = parent * 2 + 1;
//				}
//				else
//				{
//					break;
//				}
//			}
//		}
//
//		//堆的删除
//		void pop()
//		{
//			swap(_con[0], _con[_con.size() - 1]);//首尾交换
//			_con.pop_back();//删除尾部数据
//
//			adjust_down(0);//向下调整
//		}
//
//		const T& top()
//		{
//			return _con[0];
//		}
//
//		size_t size()
//		{
//			return _con.size();
//		}
//
//		bool empty()
//		{
//			return _con.empty();
//		}
//
//
//		template<class InputIterator>
//		priority_queue(InputIterator first, InputIterator last)
//		{
//			while (first != last)
//			{
//				_con.push_back(*first);
//				++first;
//			}
//
//			//直接建堆
//			//向下调整
//			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
//			{
//				adjust_down(i);
//			}
//
//		}
//
//	private:
//		Container _con;
//	};
//}

// 使用仿函数实现priority_queue
//仿函数的使用场景
namespace xlf
{
	template<class T>
	class myless
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	class mygreat
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

	//通过外部来改变排序的规则，而不是在内部改变 >  < 的符号来控制 
	template<class T, class Container = vector<T>, class Comapre = myless<int>>
	class priority_queue
	{
	public:
		//强制编译器生成默认构造
		priority_queue() = default;

		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}
			//直接建堆
			//向下调整
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}

		}


		//用 < 实现大堆
		void adjust_up(int child)
		{
			Comapre comfunc;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (comfunc(_con[parent], _con[child]))
					//if (Comapre.operator()(_con[parent] , _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}

		}

		//堆的插入
		void push(const T& x)
		{
			_con.push_back(x);//由这个函数进行扩容

			//向上调整
			adjust_up(_con.size() - 1);//排序的区间长度
		}

		void adjust_down(size_t parent)
		{
			Comapre comfunc;
			size_t child = parent * 2 + 1;//左孩子
			while (child < _con.size())
			{
				//假设法
				//选择左右孩子大的那个
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1]))
				{
					++child;
				}
				//if (_con[parent] < _con[child])
				if (comfunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}


		//堆的删除
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);//首尾交换
			_con.pop_back();//删除尾部数据

			adjust_down(0);//向下调整
		}

		const T& top()
		{
			return _con[0];
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

	private:
		Container _con;
	};

}